package cmlabs.numbertheoryutils.algorithms;

import cmlabs.numbertheoryutils.Functions;

import java.math.BigInteger;

/**
 * Created by IntelliJ IDEA.
 * User: jte
 * Date: 14.4.11
 * Time: 23.24
 * To change this template use File | Settings | File Templates.
 */
public class ChineseRemainderTheorem {

    public static BigInteger solve(int []a, int []n){
        if (a.length != n.length || a.length == 0 || !Functions.areCoprime(n)){
            throw new IllegalArgumentException();
        }
        int []x = new int[a.length];
        for (int i = 0; i < a.length; ++i){
            a[i] = Functions.mod(a[i], n[i]);
        }
        for (int i = 0; i < a.length; ++i){
            x[i] = a[i];
            for (int j = 0; j < i; ++j){
                x[i] = Functions.mod(Functions.reverseElement(n[i], n[j]) * (x[i] - x[j]), n[i]);
            }
        }
        BigInteger result = BigInteger.ZERO;
        for (int i = 0; i < x.length; ++i){
            BigInteger current = BigInteger.valueOf(x[i]);
            for (int j = 0; j < i; ++j) {
                current = current.multiply(BigInteger.valueOf(n[j]));
            }
            result = result.add(current);
        }
        return result;
    }
}
